package 算法模板;

/**
 *
 */
public class 树状数组 {

    public static void main(String[] args) {

        int[] nums = {0, 9, 5, 7, 3};
        TreeArray treeArray = new TreeArray(nums);
//        System.out.println(treeArray.sumRange(4, 4));
//        System.out.println(treeArray.sumRange(2, 4));
//        System.out.println(treeArray.sumRange(3, 3));
//        treeArray.update(4, 5);
//        treeArray.update(1, 7);
//        treeArray.update(0, 8);
//        System.out.println(treeArray.sumRange(1, 2));

        treeArray.query(4);

    }

}

class TreeArray {

    int[] treeArray;

    int[] numArray;

    // 初始化数状数组
    public TreeArray(int[] nums) {
        treeArray = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            // 数组数组的索引需要从1开始
            add(i + 1, nums[i]);
        }
        numArray = nums;
    }

    // 获取到num二进制的最后一位1 如果num=2 -> 1 0 -> 1 0
    public int lowBit(int num) {
        return num & -num;
    }

    // 查询前缀和的方法
    public int query(int index) {
        int ans = 0;
        for (int curIndex = index; curIndex > 0; curIndex -= lowBit(curIndex)) {
            ans += treeArray[curIndex];
        }
        return ans;
    }

    // 在数状数组index位置中增加值value
    public void add(int index, int value) {
        for (int curIndex = index; curIndex < treeArray.length; curIndex += lowBit(curIndex)) {
            treeArray[curIndex] += value;
        }
    }

    // 修改某一个索引的值
    public void update(int index, int value) {
        // 原来的值为numArray[i]，如果需要变成value，需要 +value-numArray[i]
        add(index + 1, value - numArray[index]);
        numArray[index] = value;
    }

    public int sumRange(int left, int right) {
        // [0,right]的和减去[0,left-1]的和
        return query(right + 1) - query(left);
    }

}